package LeetCode.leetcode;

/**
 * X的平方根
 * @author: leiwenkang02@meituan.com
 * @date: 2018/8/24
 * @time: 11:09
 */
public class Test69x的平方根 {
    public static void main(String[] args) {
        System.out.println(mySqrt(8));
    }

    public static int mySqrt(int x) {
        long start = 0;
        long end = x;
        while (start <= end) {
            long mid = (start + end) / 2;
            if (mid * mid == x) {
                return (int)mid;
            } else if (mid * mid < x) {
                if ((mid + 1) * (mid + 1) > x) {
                    return (int)mid;
                } else {
                    start = mid + 1;
                }
            } else {
                if ((mid - 1) * (mid - 1) < x) {
                    return (int)(mid - 1);
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}

